﻿using System;
using System.Collections;

namespace CatEars.Core.Collections.Search
{
    /// <summary>
    /// 二分搜素和插入
    /// </summary>
    public static class BinarySearch
    {
        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="source">数据源【NotNull】</param>
        /// <param name="keySelector">获取对比键委托【NotNull】</param>
        /// <param name="key">键值【NotNull】</param>
        /// <param name="result">结果输出</param>
        /// <returns>是否搜索到</returns>
        public static bool Search<TObject, TKey>(
            IList source,
            Func<TObject, TKey> keySelector,
            IComparable key,
            out TObject result)
            where TKey : IComparable
        {
            int index;
            return Search(source, keySelector, key, out result, out index);
        }

        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="source">数据源【NotNull】</param>
        /// <param name="keySelector">获取对比键委托【NotNull】</param>
        /// <param name="key">键值【NotNull】</param>
        /// <param name="result">结果输出</param>
        /// <param name="intIndex">结果所在位置</param>
        /// <returns>是否搜索到</returns>
        public static bool Search<TObject, TKey>(
            IList source,
            Func<TObject, TKey> keySelector,
            IComparable key,
            out TObject result,
            out int intIndex)
            where TKey : IComparable
        {
            int intLowIndex = 0;
            int intHeightIndex = source.Count - 1;
            return Search(source, keySelector, key, out result, out intIndex, intLowIndex, intHeightIndex) != -1;
        }

        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="source">数据源【NotNull】</param>
        /// <param name="keySelector">获取对比键委托【NotNull】</param>
        /// <param name="key">键值【NotNull】</param>
        /// <param name="result">结果输出</param>
        /// <param name="index">结果所在位置</param>
        /// <param name="intLowIndex">开始位置</param>
        /// <param name="intHeightIndex">结束位置</param>
        /// <returns>所在位置</returns>
        private static int Search<TObject, TKey>(
            IList source,
            Func<TObject, TKey> keySelector,
            IComparable key,
            out TObject result,
            out int index,
            int intLowIndex,
            int intHeightIndex)
            where TKey : IComparable
        {
            result = default(TObject);
            index = -1;
            while (intLowIndex <= intHeightIndex)
            {
                int middleIndex = (intLowIndex + intHeightIndex) / 2;
                TObject obj = (TObject)source[middleIndex];
                IComparable key2 = keySelector(obj);
                int compareResult = key.CompareTo(key2);
                if (compareResult == 0)
                {
                    result = obj;
                    index = middleIndex;
                    return middleIndex;
                }
                else if (compareResult < 0)
                {
                    intHeightIndex = middleIndex - 1;
                }
                else
                {
                    intLowIndex = middleIndex + 1;
                }
            }
            return -1;
        }

        /// <summary>
        /// 计算二分查找插入点
        /// </summary>
        /// <param name="source">数据源【NotNull】</param>
        /// <param name="keySelector">获取对比键委托【NotNull】</param>
        /// <param name="key">键值【NotNull】</param>
        /// <param name="keepOrder">ture 插入在相同Key对象的后面；false 随便插入，保证key的顺序即可</param>
        /// <returns>返回值</returns>
        public static int FindInsertIndex<TObject, TKey>(
            IList source,
            Func<TObject, TKey> keySelector,
            TKey key,
            bool keepOrder)
            where TKey : IComparable
        {
            int resultIndex = 0;
            int lowIndex = 0;
            int heightIndex = source.Count - 1;
            while (lowIndex <= heightIndex)
            {
                int middleIndex = (lowIndex + heightIndex) / 2;
                TObject obj = (TObject)source[middleIndex];
                IComparable key2 = keySelector(obj);

                int compareResult = key.CompareTo(key2);
                if (compareResult == 0)
                {
                    resultIndex = middleIndex;
                    break;
                }
                else if (compareResult < 0)
                {
                    heightIndex = middleIndex - 1;
                    resultIndex = heightIndex + 1;
                }
                else
                {
                    lowIndex = middleIndex + 1;
                    resultIndex = lowIndex;
                }
            }
            //到这里只是找到了TKey等于指定key的位置，要保持顺序插入，需要往后找一个比key大的对象
            if (keepOrder)
            {
                int i = resultIndex;
                for (; i < source.Count; i++)
                {
                    TObject obj = (TObject)source[i];
                    IComparable key2 = keySelector(obj);
                    int compareResult = key2.CompareTo(key);
                    if (compareResult > 0)
                    {
                        return i;
                    }
                }
                return i;
            }
            return resultIndex;
        }
    }
}
